package com.fanshuai.algorithms.twopointer;

public class TwoPointer {
    static class ListNode {
        int value;
        ListNode next;

        public ListNode(int value) {
            this.value = value;
            this.next = null;
        }
    }

    private static ListNode buildList(int[] a, int cycleIndex) {
        ListNode[] arr = new ListNode[a.length];
        for (int i = 0; i < a.length; i++) {
            ListNode node = new ListNode(a[i]);
            arr[i] = node;

            if (i > 0) {
                arr[i - 1].next = arr[i];
            }
        }
        //构成环
        if (cycleIndex >= 0 && cycleIndex < a.length) {
            arr[a.length - 1].next = arr[cycleIndex];
        }

        return arr[0];
    }

    private static void printList(ListNode listNode) {
        ListNode node = listNode;

        int count = 0;
        while (node != null && count < 2000) {
            System.out.print(node.value + " ");
            node = node.next;

            count++;
        }
        System.out.println();
    }

    /**
     * 判断链表是否有环
     */
    public static boolean hasCycle(ListNode head) {
        if (null == head) {
            return false;
        }
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }

        return false;
    }

    /**
     * 判断环的起始位置
     */
    public static ListNode detectCycle(ListNode head) {
        if (null == head) {
            return null;
        }
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                break;
            }
        }

        if (null == fast) {
            return null;
        }
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    /**
     * 寻找链表中间节点
     */
    public static ListNode findMediumNode(ListNode head) {
        if (null == head) {
            return null;
        }
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

    /**
     * 寻找倒数第k个节点
     */
    public static ListNode findLastKNode(ListNode head, int k) {
        if (null == head) {
            return null;
        }

        ListNode fast = head, slow = head;
        while (k-- > 0 && fast != null) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    /**
     * 两数之和  数组升序排列
     */
    public static int[] findTwoSum(int[] a, int sum) {
        int i = 0, j = a.length - 1;
        while (i < j) {
            int add = a[i] + a[j];
            if (add == sum) {
                return new int[]{i, j};
            } else if (add < sum) {
                i++;
            } else {
                j--;
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 翻转数组
     */
    public static void reverseArray(int[] a) {
        int i = 0, j = a.length - 1;
        while (i < j) {
            swap(a, i, j);
            i++;
            j--;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        //testCycleList();
        testArrayPointer();
    }

    private static void testCycleList() {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        ListNode node = buildList(a, 2);

        printList(node);

        System.out.println(hasCycle(node));
        ListNode cycleStart = detectCycle(node);
        System.out.println(cycleStart.value);

        ListNode node1 = buildList(a, -1);
        printList(node1);

        ListNode medium = findMediumNode(node1);
        System.out.println(medium.value);

        ListNode lastK = findLastKNode(node1, 2);
        System.out.println(lastK.value);
        lastK = findLastKNode(node1, 4);
        System.out.println(lastK.value);
    }

    private static void testArrayPointer() {
        int[] a = {1, 2, 2, 3, 5, 5, 6, 7, 7, 9};
        int[] pos = findTwoSum(a, 7);

        System.out.println(pos[0] + ", " + pos[1]);

        reverseArray(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.print("\n");
    }
}
